Какова Алгоритмическая Сложность?
Алгоритмическая сложность, (вычислительная сложность, или сложность Кольмогорова), основополагающая идея в обоих вычислительная теория сложности и алгоритмическая информационная теория , и играет важную роль в формальной индукции.
алгоритмическая сложность двойной последовательности определен как самая короткая и самая эффективная программа, которая может произвести последовательность. Хотя есть бесконечное число программ, которые могут произвести любую данную последовательность, одна программа или группа программ всегда будут самыми короткими. Нет никакого алгоритмического способа найти самый короткий алгоритм что выходы данная последовательность; это - один из первых результатов вычислительной теории сложности. Даже в этом случае, мы можем высказать образованное предположение. Этот результат, (вычислительная сложность последовательности), оказывается, очень важен для непроницаемостей, связанных с исчисляемостью.
Так как любой физический объект или свойство могут в принципе быть описаны почти истощению последовательностью оспин, у объектов и свойств, как могут говорить, есть алгоритмическая сложность также. Фактически, восстанавливание сложности реальных объектов к программам, которые производят объекты как выход, является одним способом рассмотреть предприятие науки. Составные объекты вокруг нас имеют тенденцию прибывать из трех главных процессов производства; появление , развитие , и интеллект , с объектами, произведенными каждой охраной к большей алгоритмической сложности.
Вычислительная сложность - понятие, часто используемое в теоретической информатике, чтобы определить относительную трудность вычисления растворов широких классов математических и логических проблем. Больше чем 400 классов сложности существуют, и дополнительные классы непрерывно обнаруживаются. Известный <прочный> P = NP вопрос касается природы двух из этих классов сложности. Классы сложности включают проблемы, намного более трудные чем что-либо, чему можно было бы противостоять в математике до исчисления. Есть много вообразимых проблем в вычислительной теории сложности, которая потребовала бы, чтобы почти бесконечное количество времени решило.
Алгоритмическая сложность и связанные понятия были разработаны в 1960 с десятками исследователей. Андрей Кольмогоров, Рей Соломонофф и Грегори Чэйтин сделали существенные вклады в последних 60 с с алгоритмической информационной теорией. Принцип минимальной длины сообщения, тесно связанной с алгоритмической сложностью, обеспечивает большую часть фундамента статистического и индуктивного вывода и машинного изучения.